Tutorial summary Reductions in machine learning.

Exploiting contexts to deal with uncertainty in classification.

Guest editorial special issue on utility%2Dbased data mining.

High%2Dquantile modeling for customer wallet estimation and other applications.
In this paper we discuss the important practical problem of customer wallet estimation, i.e., estimation of potential spending by customers (rather than their expected spending). For this purpose we utilize quantile modeling, whose goal is to estimate a quantile of the discriminative conditional distribution of the response, rather than the mean, which is the implicit goal of most standard regression approaches. We argue that a notion of wallet can be captured through high quantile modeling (e.g, estimating the 90th percentile), and describe a wallet estimation implementation within IBM’s Market Alignment Program (MAP). We also discuss the wide range of domains where high-quantile modeling can be practically important: estimating opportunities in sales and marketing domains, defining ’surprising’ patterns for outlier and fraud detection and more. We survey some existing approaches for quantile modeling, and propose adaptations of nearest-neighbor and regression-tree approaches to quantile modeling. We demonstrate the various models ’ performance in high quantile estimation in several domains, including our motivating problem of estimating the ’realistic ’ IT wallets of IBM customers.
Ranking%2Dbased evaluation of regression models.

Using secure coprocessors for privacy preserving collaborative data mining and analysis.
secure coprocessors for privacy preserving
Outlier detection by active learning.

Predicting Conditional Quantiles via Reduction to Classification.
We show how to reduce the process of predicting conditional quantiles (and the median in particular) to solving classification. The accompanying theoretical statement shows that the regret of the classifier bounds the regret of the quantile regression under a quantile loss. We also test this reduction empirically against existing quantile regression methods on large real-world datasets and discover that it provides state-of-theart performance. 1
UBDM 2006 Utility%2DBased Data Mining 2006 workshop report.

Weighted One%2DAgainst%2DAll.
3 TTI-Chicago Abstract. A reduction converts a solver for one task into a solver for another task. We introduce a notion of reduction and analyze reductions between different classification tasks. 1 Introduction There are many natural supervised learning tasks; even classification comes in a variety of different forms (binary, multiclass, cost-sensitive, importance weighted, etc.) There are two approaches that one can take: The first is to analyze all tasks independently and devise algorithms for each. The other approach is to use reductions to convert new, unexplored tasks to tasks that have been thoroughly analyzed, automatically transferring existing theory and algorithms from well-understood domains into new domains. We investigate the latter approach for classification problems. Reductions can be a powerful tool with a number of desirable properties: 1. They show how similar different tasks are. If two tasks are reducible to one
Business Performance Management System for CRM and Sales Execution.

Ranking%2DBased Evaluation of Regression Models.

An Improved Categorization of Classifier%27s Sensitivity on Sample Selection Bias.
A recent paper categorizes classifier learning algorithms according to their sensitivity to a common type of sample selection bias where the chance of an example being selected into the training sample depends on its feature vector   but not (directly) on its class label y. A classifier learner is categorized as &#034;local&#034; if it is insensitive to this type of sample selection bias, otherwise, it is considered &#034;global&#034;. In that paper, the true model is not clearly distinguished from the model that the algorithm outputs. In their discussion of Bayesian classifiers, logistic regression and hard-margin support vector machines, the true model (or the model that generates the true class label for every example) is implicitly assumed to be contained in the model space of the learner, and the true class probabilities and model estimated class probabilities are assumed to asymptotically converge as the training data set size increases. However, in the discussion of naive Bayes, decision trees and soft-margin support vector machines, the model space is assumed not to contain the true model, and these three classification algorithms are instead argued to be &#034;global learners&#034;. Here we argue that most classifier learning algorithms including those just discussed may or may not be affected by sample selection bias; this will depend on the dataset as well as the heuristics or inductive bias implied by the classifier learning algorithm and their appropriateness to the particular dataset. We make use of our earlier experimental results and produce additional results to illustrate our claims.
Relating reinforcement learning performance to classification performance.

Error limiting reductions between classification tasks.
We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ɛ then the cost-sensitive classifier has cost at most 2ɛ times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning. 1
Report on UBDM%2D05 Workshop on Utility%2DBased Data Mining.

Learning and evaluating classifiers under sample selection bias.
Classifier learning methods commonly assume  that the training data consist of randomly  drawn examples from the same distribution  as the test examples about which  the learned model is expected to make predictions.
An iterative method for multi%2Dclass cost%2Dsensitive learning.
Cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. In this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. This algorithm is derived using three key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. We establish some theoretical guarantees concerning the performance of this method. In particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. We also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.


Empirical Comparison of Various Reinforcement Learning Strategies for Sequential Targeted Marketing.
We empirically evaluate the performance of various reinforcement learning methods in applications to sequential targeted marketing. In particular, we propose and evaluate a progression of reinforcement learning methods, ranging from the &#034;direct&#034; or &#034;batch&#034; methods to &#034;indirect&#034; or &#034;simulation based&#034; methods, and those that we call &#034;semidirect &#034; methods that fall between them. We conduct a number of controlled experiments to evaluate the performance of these competing methods. Our results indicate that while the indirect methods can perform better in a situation in which nearly perfect modeling is possible, under the more realistic situations in which the system&#039;s modeling parameters have restricted attention, the indirect methods&#039; performance tend to degrade. We also show that semi-direct methods are effective in reducing the amount of computation necessary to attain a given level of performance, and often result in more profitable policies.
Sequential cost%2Dsensitive decision making with reinforcement learning.
Recently, there has been increasing interest in the issues of cost-sensitive learning and decision making in a variety of applications of data mining. A number of approaches have been developed that are effective at optimizing cost-sensitive decisions when each decision is considered in isolation. However, the issue of sequential decision making, with the goal of maximizing total benefits accrued over a period of time instead of immediate benefits, has rarely been addressed. In the present paper, we propose a novel approach to sequential decision making based on the reinforcement learning framework. Our approach attempts to learn decision rules that optimize a sequence of cost-sensitive decisions so as to maximize the total benefits accrued over time. We use the domain of targeted marketing as a testbed for empirical evaluation of the proposed method. We conducted experiments using approximately two years of monthly promotion data derived from the well-known KDD Cup 1998 donation data set. The experimental results show that the proposed method for optimizing total accrued benefits outperforms the usual targeted-marketing methodology of optimizing each promotion in isolation. We also analyze the behavior of the targeting rules that were obtained and discuss their appropriateness to the application domain.
Transforming classifier scores into accurate multiclass probability estimates.
Class membership probability estimates are important for many applications of data mining in which classification outputs are combined with other sources of information for decision-making, such as example-dependent misclassification costs, the outputs of other classifiers, or domain knowledge. Previous calibration methods apply only to two-class problems. Here, we show how to obtain accurate probability estimates for multiclass problems by combining calibrated binary probability estimates. We also propose a new method for obtaining calibrated two-class probability estimates that can be applied to any classifier that produces a ranking of examples. Using naive Bayes and support vector machine classifiers, we give experimental results from a variety of two-class and multiclass domains, including direct marketing, text categorization and digit recognition.

Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers.
Accurate, well-calibrated estimates of class membership probabilities are needed in many supervised learning applications, in particular when a cost-sensitive decision must be made about examples with example-dependent costs. This paper presents simple but successful methods for obtaining calibrated probability estimates from decision tree and naive Bayesian classifiers. Using the large and challenging KDD&#039;98 contest dataset as a testbed, we report the results of a detailed experimental comparison of ten methods, according to four evaluation measures. We conclude that binning succeeds in significantly improving naive Bayesian probability estimates, while for improving decision tree probability estimates, we recommend smoothing by -estimation and a new variant of pruning that we call curtailment.

